package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;
import data_structure.helper.SwapArray;

import java.util.Arrays;

public class BubbleSort {

    private BubbleSort() {

    }

    public static <E extends Comparable<E>> void sort(E []arr){
        //第i伦循环开始时，arr[n-i+1,n)已经排好序，结束后，在数组末端有i个元素已经排好序,一共进行arr.length-1次循环
        for(int i=0;i+1<arr.length;i++){

            for(int j=0;j+1<arr.length-i;j++){
                //从开头每次对彼此相邻的两个元素进行处理
                if(arr[j].compareTo(arr[j+1])>0){
                    SwapArray.swap (arr,j,j+1);
                }
                //arr[n-i,n)
            }
        }
    }

    /**
     * 优化：
     * 在经过一次循环后，数组可能已经排好序了，此时排序结束
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2(E []arr){
        //第i伦循环开始时，arr[n-i+1,n)已经排好序，结束后，在数组末端有i个元素已经排好序,一共进行arr.length-1次循环
        for(int i=0;i+1<arr.length;i++){
            boolean isSwapped=false;
            for(int j=0;j+1<arr.length-i;j++){
                //从开头每次对彼此相邻的两个元素进行处理
                if(arr[j].compareTo(arr[j+1])>0){
                    SwapArray.swap (arr,j,j+1);
                    isSwapped = true;
                }//arr[n-i,n)
            }
            //如果在一次循环中没有交换过元素，表名此时数组已经排好序
            if(!isSwapped)break;
        }
    }

    /**
     * 进一步优化：
     * 每一次循环，就多一个元素被排好序
     * 但是，实际上，再一次循环之后，可能有多个元素被排好序
     * 我们要找到的是最后一次进行交换时的位置
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort3(E []arr){

        //第i伦循环开始时，arr[n-i+1,n)已经排好序，结束后，在数组末端有i个元素已经排好序,一共进行arr.length-1次循环
        for(int i=0;i+1<arr.length;){
            int lastSwappedIndex=0;
            for(int j=0;j+1<arr.length-i;j++){
                //从开头每次对彼此相邻的两个元素进行处理
                if(arr[j].compareTo(arr[j+1])>0){
                    SwapArray.swap (arr,j,j+1);
                    lastSwappedIndex=j+1;
                }//arr[n-i,n)
            }
            //如果在一次循环中没有交换过元素，表名此时数组已经排好序
            i=arr.length-lastSwappedIndex;
        }
    }

    public static void main(String[] args) {
        int n=10000;
        Integer []arr1= ArrayGenerator.generateNormalArray (n,n);
        Integer[]arr2= Arrays.copyOf(arr1, arr1.length);
        Integer[]arr3= Arrays.copyOf(arr1, arr1.length);

        SortingHelper.testSorting (arr1,"BubbleSort");
        SortingHelper.testSorting (arr2,"BubbleSort2");
        SortingHelper.testSorting(arr3,"BubbleSort3");
    }
}
